package com.theeviljames.seminar3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

public class GA {

//	A solution to this is 1*3*4*5*6 = 360 and 2+7+8+9+10 = 36
	
	
	private static final int multGoal = 360;
	private static final int addGoal = 36;
	//True for add, false for multiply
	private boolean[][] population;
	private static Random rand = new Random();
	private static final double mutateRate = 0.3;
	private int generation = 1;
	private int maxGenerations;
	private int popSize;
	private boolean singleCrossover;
	
	public GA(int popSize, int maxGenerations, boolean singleCrossover){	
		this.popSize = popSize;
		this.singleCrossover = singleCrossover;
		this.maxGenerations = maxGenerations;
		population = new boolean[popSize][10];
		for(int i = 0; i < population.length; i++){
			boolean[] individual = new boolean[10];
			for(int j = 0; j < 10; j++){
				individual[j] = flip();
			}
			population[i] = individual;
		}
		boolean[] solution = solve();
		if(solution == null){
			System.out.println("No solution found");
		}
		else{
			System.out.println("The following numbers sum to 36>\n");
			for(int i = 0; i < solution.length; i++){
				if(solution[i])System.out.println(i+1);
			}
			System.out.println("\nThe product of the following numbers is 360>\n");
			for(int i = 0; i < solution.length; i++){
				if(!solution[i])System.out.println(i+1);
			}
			System.out.println("\nThis took " + generation + " generations with a population size of " + popSize + " to find");
		}
	}
	
	public boolean[] solve() {
		for(int i = 0; i < population.length; i++){
			if(fitness(population[i])==0.0)return population[i];
		}
		while(true&&generation<maxGenerations){
			boolean[][] newPopulation = new boolean[population.length][10];
			for(int i = 0; i < population.length/2; i++){
				boolean[] p1 = selectByRank();
				boolean[] p2 = selectByRank();
				boolean[][] children = crossover(p1, p2);
				if(fitness(children[0])==0.0)return children[0];
				if(fitness(children[1])==0.0)return children[1];
				newPopulation[2*i] = mutate(children[0]);
				newPopulation[(2*i)+1] = mutate(children[1]);
			}
			population = newPopulation;
			generation++;
		}
		return null;
	}
	public int getGeneration(){
		return generation;
	}
	public double fitness(boolean[] individual){
		int multSum = 1;
		int addSum = 0;
		for(int i = 0; i < 10; i ++){
			if(individual[i]){
				addSum += (i+1);
			}
			else{
				multSum = multSum*(i+1);
			}
		}
		double result = ((Math.abs(multSum-multGoal))+(Math.abs(addSum-addGoal)));
		//System.out.println(result);
		return result;
	}
	
	public boolean[] mutate(boolean[] individual){
		for(int i = 0; i < 10; i++){
			if(rand.nextDouble()<mutateRate){
				individual[i] = !individual[i];
			}
		}
		return individual;
	}
	
	public boolean[] selectByRank(){
		PriorityQueue<GenomeIndexPair> pop = new PriorityQueue<GenomeIndexPair>();
		for(int i = 0; i < population.length; i++)pop.add(new GenomeIndexPair(population[i],i,fitness(population[i])));
		GenomeIndexPair[] pop2 = new GenomeIndexPair[population.length];
		for(int i = 0; i < population.length; i++) pop2[i] = pop.remove();
		int s = ((population.length)*(population.length-1))/2;
		int p = (int)rand.nextDouble()*s;
		int n = (int)(1+Math.sqrt(1+(8*p)))/2;
		return pop2[popSize-1-n].getGenome();
	}
	
	public boolean flip(){
		return (rand.nextDouble()<0.5);
	}
	
	public boolean[][] crossover(boolean[] parent1, boolean[] parent2){
		boolean[][] result = new boolean[2][10];
		//using single point crossover
		if(singleCrossover){
			int crossover = rand.nextInt(10);
			System.arraycopy(parent1, 0, result[0], 0, crossover);
			System.arraycopy(parent2, crossover, result[0], crossover, 10-crossover);
			System.arraycopy(parent2, 0, result[1], 0, crossover);
			System.arraycopy(parent1, crossover, result[1], crossover, 10-crossover);
		}
		else{
		//uniform crossover
			for(int i = 0; i < 10; i++){
				if(flip()){
					result[0][i] = parent1[i];
					result[1][i] = parent2[i];
				}
				else{
					result[1][i] = parent1[i];
					result[0][i] = parent2[i];
				}
			}
		}
		return result;
	}
	
	public class GenomeIndexPair implements Comparable{
		
		private boolean[] genome;
		private int index;
		private double fitness;
		
		public GenomeIndexPair(boolean[] genome, int index, double fitness) {
			this.genome = genome;
			this.index = index;
			this.fitness = fitness;
		}
		public int compareTo(Object arg0) {
			GenomeIndexPair other = (GenomeIndexPair)arg0;
			if(getFitness()>other.getFitness())return -1;
			if(getFitness()<other.getFitness())return 1;
			return 0;
		}
		public double getFitness(){
			return fitness;
		}
		public boolean[] getGenome(){
			return genome;
		}
		@Override
		public String toString() {
			return "Genome> " + Arrays.toString(genome) + "\nFitness> " + fitness + "\nIndex> " + index +"\n";
		}
	}
	public static void main(String[] args) {
		GA ga = new GA(10,10000, true);
		//boolean[] solution = new boolean[]{false,true,false,false,false,false,true,true,true,true};
		//System.out.println(GA.fitness(solution));
	}
}
